package tomoto.util;

import java.util.Arrays;

import tomoto.assertion.ParamUtil;

/**
 * Substitution of {@link java.util.BitSet} that has fixed size and higher
 * performance.
 * 
 * @author tomoto
 * 
 */
public class FastBitSet implements Duplicatable<FastBitSet> {
	/** whether the parameter check is enabled */
	private static final boolean cs_paramCheckEnabled;
	static {
		cs_paramCheckEnabled = FastBitSet.class.desiredAssertionStatus();
	}

	/** bit size of a word */
	private static final int WORD_SIZE = 32;

	/** bit size */
	private int m_size;
	/** storage of bits */
	private int[] m_data;

	/**
	 * Creates a new bit set of the specified size.
	 * 
	 * @param size size in bits
	 */
	public FastBitSet(int size) {
		m_size = size;
		m_data = new int[(size + WORD_SIZE - 1) / WORD_SIZE];
	}

	/**
	 * Copy constructor.
	 */
	public FastBitSet(FastBitSet other) {
		m_size = other.m_size;
		m_data = ArrayUtil.dup(other.m_data);
	}

	/**
	 * Duplicates itself.
	 */
	public FastBitSet dup() {
		return new FastBitSet(this);
	}

	/**
	 * Returns the size.
	 * 
	 * @return as described above
	 */
	public int size() {
		return m_size;
	}

	/**
	 * Returns the raw data. You should not use this method unless you really
	 * need efficiency. Note that the bits above the specified size is not
	 * always zero-cleared but can be garbages.
	 * 
	 * @return as described above
	 */
	public int[] getData() {
		return m_data;
	}

	/**
	 * Returns the bit at the specified index.
	 * 
	 * @param index index (0 <= index < size)
	 * @return as described above
	 */
	public boolean get(int index) {
		if (cs_paramCheckEnabled) {
			ParamUtil.check(index >= 0 && index < m_size);
		}
		return (m_data[index / WORD_SIZE] & (1 << (index % WORD_SIZE))) != 0;
	}

	/**
	 * Sets or resets the bit at the specified index.
	 * 
	 * @param index index (0 <= index < size)
	 * @param value true to set or false to reset
	 */
	public void set(int index, boolean value) {
		if (cs_paramCheckEnabled) {
			ParamUtil.check(index >= 0 && index < m_size);
		}
		if (value) {
			m_data[index / WORD_SIZE] |= 1 << (index % WORD_SIZE);
		} else {
			m_data[index / WORD_SIZE] &= ~(1 << (index % WORD_SIZE));
		}
	}

	/**
	 * Applies AND operation with another bit set.
	 * 
	 * @param other bit set to AND with.
	 */
	public void and(FastBitSet other) {
		int length = Math.min(m_data.length, other.m_data.length);
		for (int i = 0; i < length; i++) {
			m_data[i] &= other.m_data[i];
		}
	}

	/**
	 * Applies OR operation with another bit set.
	 * 
	 * @param other bit set to OR with.
	 */
	public void or(FastBitSet other) {
		int length = Math.min(m_data.length, other.m_data.length);
		for (int i = 0; i < length; i++) {
			m_data[i] |= other.m_data[i];
		}
		trimGarbage();
	}

	/**
	 * Applies NAND operation with another bit set.
	 * 
	 * @param other bit set to NAND with.
	 */
	public void nand(FastBitSet other) {
		int length = Math.min(m_data.length, other.m_data.length);
		for (int i = 0; i < length; i++) {
			m_data[i] &= ~other.m_data[i];
		}
	}

	/**
	 * Applies bit inversion operation.
	 */
	public void inv() {
		for (int i = 0; i < m_data.length; i++) {
			m_data[i] = ~m_data[i];
		}
		trimGarbage();
	}

	/**
	 * Copies the data from another bit set. The sizes of both bit sets must be
	 * the same.
	 * 
	 * @param other bit set to copy from.
	 */
	public void copyFrom(FastBitSet other) {
		ParamUtil.check(m_size == other.m_size);
		System.arraycopy(other.m_data, 0, m_data, 0, other.m_data.length);
		trimGarbage();
	}

	/**
	 * Sets or resets all bits.
	 * 
	 * @param value true to set or false to reset.
	 */
	public void setAll(boolean value) {
		Arrays.fill(m_data, value ? ~0 : 0);
		trimGarbage();
	}

	/**
	 * Resets all bits.
	 */
	public void clear() {
		setAll(false);
	}

	/**
	 * Perform a left shift operation (move each bit to the next in the
	 * direction of increasing the index).
	 */
	public void lshift() {
		int prevMsb = 0;
		for (int i = 0; i < m_data.length; i++) {
			int msb = m_data[i] >>> (WORD_SIZE - 1);
			m_data[i] = (m_data[i] << 1) + prevMsb;
			prevMsb = msb;
		}
		trimGarbage();
	}

	/**
	 * Perform a right shift operation (move each bit to the next in the
	 * direction of decreasing the index).
	 */
	public void rshift() {
		int prevLsb = 0;
		for (int i = m_data.length - 1; i >= 0; i--) {
			int lsb = m_data[i] << (WORD_SIZE - 1);
			m_data[i] = (m_data[i] >>> 1) + prevLsb;
			prevLsb = lsb;
		}
	}

	/**
	 * Shifts by specified bits.
	 * 
	 * @param n number of bits to shift. Positive means left and negative means
	 *            right.
	 */
	public void shift(int n) {
		if (n > 0) {
			while (n-- > 0) {
				lshift();
			}
		} else {
			while (n++ < 0) {
				rshift();
			}
		}
	}

	private void trimGarbage() {
		int mask = ~0 >>> (WORD_SIZE - 1 - (m_size - 1) % WORD_SIZE);
		m_data[(m_size - 1) / WORD_SIZE] &= mask;
	}

	/**
	 * Counts the number of bits set to true. Not much fast.
	 * 
	 * @return as described above
	 */
	public int countBits() {
		int result = 0;
		for (int d : m_data) {
			result += NumberUtil.countBits(d);
		}
		return result;
	}

	/**
	 * Finds the first bit that has the specified value and returns its index.
	 * Not much fast.
	 * 
	 * @param value value to find
	 * @param start index to start searching
	 * @return as described above or -1 if none is found.
	 */
	public int find(boolean value, int start) {
		for (int i = start; i < m_size; i++) {
			if (get(i) == value) {
				return i;
			}
		}
		return -1;
	}

	/**
	 * {@inheritDoc}
	 */
	@Override
	public int hashCode() {
		int hash = 0;
		for (int i : m_data) {
			hash = hash * 13 + i;
		}
		return hash;
	}

	/**
	 * {@inheritDoc}
	 */
	@Override
	public boolean equals(Object other0) {
		if (other0 instanceof FastBitSet) {
			FastBitSet other = (FastBitSet) other0;
			return m_size == other.m_size && Arrays.equals(m_data, other.m_data);
		} else {
			return false;
		}
	}

	/**
	 * {@inheritDoc} Formats the bits in binary　string. Slow.
	 */
	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < m_size; i++) {
			sb.append(get(i) ? '1' : '0');
		}
		return sb.toString();
	}

}
